package leetcode_day._2022._202210._1120;

/**
 * 779. 第K个语法符号
 * 算法：找规律
 * 0
 * 01
 * 0110
 * 01101001
 * 由前四行可知, 下一行的后 (1 << (n - 2)) 个数是上一行数的相反
 * 可以由下往上推, 如果 k > (1 << (n - 2)), 则当前行的 k 是上一行第 k - (1 << (n - 2)) 的相反数(0 --> 1, 1 --> 0)
 * 反之, 当前行的 k 是上一行的 k
 *
 * @author saasyezh
 * @version 1.0
 * @date 2022/10/20 21:33
 */
public class _20_779 {

    public int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        if (k > (1 << (n - 2))) return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)));
        else return kthGrammar(n - 1, k);
    }

}
